COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	%Start Part 2 of 6 concep.tex
C00039 ENDMK
C⊗;
%Start Part 2 of 6 concep.tex
\beginSection{Inheritance}

A class can inherit methods, slots, and some {\bf defclass} options
from its superclasses.  The following sections describe the inheritance of
methods, the inheritance of slots and slot options, and the inheritance of
class options.
 
\beginsubSection{Inheritance of Methods}

A subclass inherits methods in the sense that any method applicable to
all instances of a class is also applicable to all instances of any
subclass of that class.

The inheritance of methods acts the same way regardless of whether the
method was created by using one of the method-defining forms or by
using one of the {\bf defclass} options that causes methods to be
generated automatically.

The inheritance of methods is described in detail in the section
``Method Selection and Combination.''   

\endsubSection%{Inheritance of Methods}

\beginsubSection{Inheritance of Slots and Slot Options}

The set of the names of all slots accessible in an instance of a class
$C$ is the union of the sets of names of slots defined by $C$ and its
superclasses. The {\bit structure} of an instance is the set of names
of local slots in that instance.

In the simplest case, only one class among $C$ and its superclasses
defines a slot with a given slot name.  If a slot is defined by a
superclass of $C$\negthinspace, the slot is said to be {\bit
inherited}.  The characteristics of the slot are determined by the
slot specifier of the defining class.  Consider the defining class for
a slot $S$\negthinspace.  If the value of the {\bf :allocation} slot
option is {\bf :instance}, then $S$ is a local slot and each instance
of $C$ has its own slot named $S$ that stores its own value.  If the
value of the {\bf :allocation} slot option is {\bf :class}, then $S$
is a shared slot, the class that defined $S$ stores the value, and all
instances of $C$ can access that single slot.  If the {\bf
:allocation} slot option is omitted, {\bf :instance} is used.

In general, more than one class among $C$ and its superclasses can
define a slot with a given name.  In such cases, only one slot with
the given name is accessible in an instance of $C$\negthinspace, and
the characteristics of that slot are a combination of the several slot
specifiers, computed as follows:

\beginlist

\item{\bull} All the slot specifiers for a given slot name are ordered
from most specific to least specific, according to the order in $C$'s
class precedence list of the classes that define them. All references
to the specificity of slot specifiers immediately below refers to this
ordering.

\goodbreak

\item{\bull} The allocation of a slot is controlled by the most specific
slot specifier.  If the most specific slot specifier does not contain an
{\bf :allocation} slot option, {\bf :instance} is used.  Less specific
slot specifiers do not affect the allocation.

\item{\bull} The default initial value form for a
slot is the value of the {\bf :initform} slot option in the most
specific slot specifier that contains one.  If no slot specifier
contains an {\bf :initform} slot option, the slot has no default
initial value form.

\item{\bull} The contents of a slot will always be of type {\tt
(and} $T\sub 1$ $\ldots$ $T\sub n${\tt )} where $T\sub 1 \ldots T\sub n$ are
the values of the {\bf :type} slot options contained in all of the slot
specifiers.  If no slot specifier contains the {\bf :type} slot option, the
contents of the slot will always be of type {\bf t}. The result
of attempting to store in a slot
a value that does not satisfy the type of the slot is undefined.

\item{\bull} The set of initialization arguments that initialize a given
slot is the union of the initialization arguments declared in the {\bf
:initarg} slot options in all the slot specifiers.

\item{\bull} The documentation string for a slot is the value of the
{\bf :documentation} slot option in the most specific slot specifier
that contains one.  If no slot specifier contains a {\bf
:documentation} slot option, the slot has no documentation string.

\endlist

A consequence of the allocation rule is that a shared slot can be
shadowed.  For example, if a class $C\sub 1$ defines a slot named $S$
whose value for the {\bf :allocation} slot option is {\bf :class},
that slot is accessible in instances of $C\sub 1$ and all of its
subclasses.  However, if $C\sub 2$ is a subclass of $C\sub 1$ and also
defines a slot named $S$\negthinspace, $C\sub 1$'s slot is not shared
by instances of $C\sub 2$ and its subclasses. When a class
$C\sub 1$ defines a shared slot, any subclass $C\sub 2$ of $C\sub
1$ will share this single slot unless the {\bf defclass} form for
$C\sub 2$ specifies a slot of the same name or there is a superclass
of $C\sub 2$ that precedes $C\sub 1$ in the class precedence list of
$C\sub 2$ that defines a slot of the same name.

A consequence of the type rule is that the value of a slot satisfies
the type constraint of each slot specifier that contributes to that
slot.  Because the result of attempting to store in a slot a value
that does not satisfy the type constraint for the slot is undefined,
the value in a slot might fail to satisfy its type constraint.

The {\bf :reader}, {\bf :writer}, and {\bf :accessor} slot options
create methods rather than define the characteristics of a slot.
Reader and writer  methods are inherited in the sense described in
the section ``Inheritance of Methods.'' 

Methods that access slots use only the name of the slot and the type
of the slot's value.  Suppose a superclass provides a method that
expects to access a shared slot of a given name, and a subclass defines
a local slot with the same name.  If the method provided by the
superclass is used on an instance of the subclass, the method accesses
the local slot.

\beginsubSection{Inheritance of Class Options}

The {\bf :default-initargs} class option is inherited.  The set of
defaulted initialization arguments for a class is the union of the
sets of initialization arguments specified in the {\bf
:default-initargs} class options of the class and its superclasses.
When more than one default initial value form is supplied for a given
initialization argument, the default initial value form that is used
is the one supplied by the class that is most specific according to
the class precedence list.

\newpage

If a given {\bf :default-initargs} class option specifies an
initialization argument of the same name more than once, an
error is signaled.

\endsubSection%{Inheritance of Class Options}

\beginsubSection{Examples}

\screen!

(defclass C1 () 
    ((S1 :initform 5.4 :type number) 
     (S2 :allocation :class)))

(defclass C2 (C1) 
    ((S1 :initform 5 :type integer)
     (S2 :allocation :instance)
     (S3 :accessor C2-S3)))
\endscreen!

Instances of the class {\tt C1} have a local slot named {\tt S1}, whose default
initial value is 5.4 and whose value should always be a number.
The class {\tt C1} also has a shared slot named {\tt S2}.

There is a local slot named {\tt S1} in instances of {\tt C2}.  The
default initial value of {\tt S1} is 5.  The value of {\tt S1} will be
of type {\tt (and integer number)}.  There are also local slots named
{\tt S2} and {\tt S3} in instances of {\tt C2}.  The class {\tt C2}
has a method for {\tt C2-S3} for reading the value of slot {\tt S3};
there is also a method for {\tt (setf C2-S3)} that writes the
value of {\tt S3}.

\endsubSection%{Examples of Inheritance}
\endSection%{Inheritance}

\beginSection{Integrating Types and Classes} 

The \CLOS\ maps the space of classes into the Common Lisp type space.
Every class that has a proper name has a corresponding type with the same 
name.  

The proper name of every class is a valid type specifier.  In
addition, every class object is a valid type specifier.  Thus the
expression {\tt (typep {\it object class\/})} evaluates to true if the
class of {\it object\/} is {\it class\/} itself or a subclass of {\it
class}.  The evaluation of the expression {\tt (subtypep {\it class1
class2\/})} returns the values {\bf t~t} if {\it class1\/} is a
subclass of {\it class2\/} or if they are the same class; otherwise it
returns the values {\bf nil~t}.  If $I$ is an instance of some class
$C$ named $S$ and $C$ is an instance of {\bf standard-class}, the
evaluation of the expression {\tt (type-of $I$\/)} will return $S$ if
$S$ is the proper name of $C$\negthinspace; if $S$ is not the proper
name of $C$\negthinspace, the expression {\tt (type-of $I$\/)} will
return $C$\negthinspace.

Because the names of classes and class objects are type specifiers, they may
be used in the special form {\bf the} and in type declarations.

Many but not all of the predefined Common Lisp type specifiers have a
corresponding class with the same proper name as the type.  These type
specifiers are listed in Figure~1-1.  For example, the type {\bf array}
has a corresponding class named {\bf array}.  No type specifier that is a
list, such as {\tt (vector double-float 100)}, has a corresponding class.
The form {\bf deftype} does not create any classes.

Each class that corresponds to a predefined Common Lisp type specifier
can be implemented in one of three ways, at the discretion of each
implementation.  It can be a {\bit standard class\/} (of the kind
defined by {\bf defclass}), a {\bit structure class\/} (defined
by {\bf defstruct}), or a {\bit built-in class\/} (implemented in
a special, non-extensible way).

A built-in class is one whose instances have restricted capabilities or
special representations.  Attempting to use {\bf defclass} to define 
subclasses of a built-in class signals an error.  Calling {\bf
make-instance} to create an instance of a built-in class signals an error.
Calling {\bf slot-value} on an instance of a built-in class signals an
error.  Redefining a built-in class or using {\bf change-class} to change
the class of an instance to or from a built-in class signals an error.
However, built-in classes can be used as parameter specializers in
methods.

%The \OS\ specifies that all predefined Common Lisp type specifiers
%listed in Figure~1-1 are built-in classes, but a particular
%implementation is allowed to extend the \OS\ to define some of them as
%standard classes or as structure classes.

It is possible to determine whether a class is a built-in class by
checking the metaclass.  A standard class is an instance of {\bf
standard-class}, a built-in class is an instance of {\bf
built-in-class}, and a structure class is an instance of {\bf
structure-class}.

Each structure type created by {\bf defstruct} without using the {\bf
:type} option has a corresponding class.  This class is an instance of
{\bf structure-class}.  
%A portable program must assume that {\bf
%structure-class} is a subclass of {\bf built-in-class} and has the
%same restrictions as built-in classes.  Whether {\bf structure-class}
%in fact is a subclass of {\bf built-in-class} is
%implementation dependent. 
The {\bf :include} option of {\bf defstruct} creates a direct
subclass of the class that corresponds to the included structure.

The purpose of specifying that many of the standard Common Lisp type
specifiers have a corresponding class is to enable users to write methods that
discriminate on these types.  
Method selection requires that a class precedence list can be
determined for each class. 

\vfill\eject
The hierarchical relationships among the Common Lisp type specifiers
are mirrored by relationships among the classes corresponding to those
types.  The existing type hierarchy is used for determining the
class precedence list for each class that corresponds to a predefined
Common Lisp type.  In some cases, {\it Common Lisp: The Language\/}
does not specify a local precedence order for two supertypes of a
given type specifier.  For example, {\bf null} is a subtype of both
{\bf symbol} and {\bf list}, but {\it Common Lisp: The Language\/}
does not specify whether {\bf symbol} is more specific or less
specific than {\bf list}.  The \CLOS\ specification defines those
relationships for all such classes.

The following figure lists the set of classes required by the \OS\
that correspond to predefined Common Lisp type specifiers.  The
superclasses of each such class are presented in order from most
specific to most general, thereby defining the class precedence list
for the class. The local precedence order for each class that
corresponds to a Common Lisp type specifier can be derived from this
table.

\boxfig
{\dimen0=.75pc
\tabskip \dimen0 plus .5 fil
\halign to \hsize {#\hfil\tabskip \dimen0 plus 1fil&#\hfil\tabskip \dimen0 plus .5 fil&&#\hfil\cr  %was &&#
\noalign{\vskip -9pt}
\hfil\bf  Predefined Common Lisp Type&\bf Class Precedence List for Corresponding Class\span\omit\span\omit\cr
\noalign{\vskip 2pt\hrule\vskip 2pt}
array&(array t)\cr
bit-vector&(bit-vector vector array sequence t)\cr
character&(character t)\cr
complex&(complex number t)\cr
cons&(cons list sequence t)\cr
float&(float number t)\cr
integer&(integer rational number t)\cr
list&(list sequence t)\cr
null&(null symbol list sequence t)\cr
number&(number t)\cr
ratio&(ratio rational number t)\cr
rational&(rational number t)\cr
sequence&(sequence t)\cr
string&(string vector array sequence t)\cr
symbol&(symbol t)\cr
t&(t)\cr
vector&(vector array sequence t)\cr
\noalign{\vskip -9pt}
}}
\caption{}
\endfig

Individual implementations may be extended to define other type
specifiers to have a corresponding class.  Individual implementations
can be extended to add other subclass relationships and to add other
elements to the class precedence lists in the above table, as long as
they do not violate the type relationships and disjointness
requirements specified by {\it Common Lisp: The Language\/}.
A standard class defined with no direct superclasses is guaranteed to
be disjoint from all of the classes in the table, except for the
class named {\bf t}.

\newpage

The following Common Lisp types will have corresponding classes when
Common Lisp is modified to define them each as being disjoint from {\bf
cons}, {\bf symbol}, {\bf array}, {\bf number}, and {\bf character}:

\beginlist

\item{\bull} function
\item{\bull} hash-table
\item{\bull} package
\item{\bull} pathname
\item{\bull} random-state
\item{\bull} readtable
\item{\bull} stream

\endlist

\endSection%{Integrating Types and Classes}

\beginSection{Determining the Class Precedence List}

The {\bf defclass} form for a class provides a total ordering on that
class and its direct superclasses.  This ordering is called the {\bit
local precedence order}.  It is an ordered list of the class and its
direct superclasses. The {\bit class precedence list\/} for a
class $C$ is a total ordering on $C$ and its superclasses that is consistent
with the local precedence orders for each of $C$ and its superclasses.

A class precedes its direct superclasses, and a
direct superclass precedes all other direct superclasses specified to
its right in the superclasses list of the {\bf defclass} form.  For
every class $C$, define $$R\sub C=\{(C,C\sub 1),(C\sub 1,C\sub
2),\ldots,(C\sub {n-1},C\sub n)\}$$ where $C\sub 1,\ldots,C\sub n$ are
the direct superclasses of $C$ in the order in which
they are mentioned in the {\bf defclass} form. These ordered pairs
generate the total ordering on the class $C$ and its direct
superclasses.

Let $S\sub C$ be the set of $C$ and its superclasses. Let $R$ be
$$R=\bigcup\sub{c\in {S\sub C}}R\sub c$$

The set $R$ may or may not generate a partial ordering, depending on
whether the $R\sub c$, $c\in S\sub C$, are consistent; it is assumed
that they are consistent and that $R$ generates a partial ordering.
When the $R\sub c$ are not consistent, it is said that $R$ is inconsistent.

%This partial ordering is generated by taking the the transitive
%closure of the set $R\cup \{(c,c) \vert c\in {S\sub C}\}$.  When
%$(C\sub 1,C\sub 2)\in R$\negthinspace, it is said that $C\sub 1$ 
%{\bit precedes or equals} $C\sub 2$.  Intuitively, $C\sub 1$ precedes
%or equals $C\sub 2$ when $C\sub 1=C\sub 2$ or $C\sub 2$ is a
%superclass of $C\sub 1$.  
%
%Recall that a partial ordering of the set $S$ is a relation between 
%objects of $S$ that is transitive, reflexive, and antisymmetric. The 
%set $\{(c,c) \vert c\in {S\subC}\}$ was added to the transitive 
%closure of the set $R$ in order to make the relation reflexive.  In 
%the remainder of this section the set of precedence relations $R$ and 
%not the partial ordering will be used.

To compute the class precedence list for~$C$\negthinspace,
topologically sort the elements of $S\sub C$ with respect to the
partial ordering generated by $R$\negthinspace.  When the topological
sort must select a class from a set of two or more classes, none of
which are preceded by other classes with respect to~$R$\negthinspace,
the class selected is chosen deterministically, as described below.

If $R$ is inconsistent, an error is signaled.


\goodbreak

\beginsubSection{Topological Sorting}

Topological sorting proceeds by finding a class $C$ in~$S\sub C$ such
that no other class precedes that element according to the elements
in~$R$\negthinspace.  The class $C$ is placed first in the result.
Remove $C$ from $S\sub C$, and remove all pairs of the form $(C,D)$,
$D\in S\sub C$, from $R$\negthinspace. Repeat the process, adding
classes with no predecessors to the end of the result.  Stop when no
element can be found that has no predecessor.

If $S\sub C$ is not empty and the process has stopped, the set $R$ is
inconsistent. If every class in the finite set of classes is preceded
by another, then $R$ contains a loop. That is, there is a chain of
classes $C\sub 1,\ldots,C\sub n$ such that $C\sub i$ precedes
$C\sub{i+1}$, $1\leq i<n$, and $C\sub n$ precedes $C\sub 1$.

Sometimes there are several classes from $S\sub C$ with no
predecessors.  In this case select the one that has a direct
subclass rightmost in the class precedence list computed so far.
Because a direct superclass precedes all other direct superclasses to
its right, there can be only one such candidate class. If there is no
such candidate class, $R$ does not generate a partial ordering---the
$R\sub c$, $c\in S\sub C$, are inconsistent.

In more precise terms, let $\{N\sub 1,\ldots,N\sub m\}$, $m\geq 2$, be
the classes from $S\sub C$ with no predecessors.  Let $(C\sub
1\ldots C\sub n)$, $n\geq 1$, be the class precedence list
constructed so far.  $C\sub 1$ is the most specific class, and $C\sub
n$ is the least specific.  Let $1\leq j\leq n$ be the largest number
such that there exists an $i$ where $1\leq i\leq m$ and $N\sub i$
is a direct superclass of $C\sub j$; $N\sub i$ is placed next.

The effect of this rule for selecting from a set of classes with no
predecessors is that the classes in a simple superclass chain are
adjacent in the class precedence list and that classes in each
relatively separated subgraph are adjacent in the class
precedence list. For example, let $T\sub 1$ and $T\sub 2$ be subgraphs
whose only element in common is the class $J$\negthinspace. Suppose
that no superclass of $J$ appears in either $T\sub 1$ or $T\sub 2$.
Let $C\sub 1$ be the bottom of $T\sub 1$; and let $C\sub 2$ be the
bottom of $T\sub 2$.  Suppose $C$ is a class whose direct superclasses
are $C\sub 1$ and $C\sub 2$ in that order, then the class precedence
list for $C$ will start with $C$ and will be followed by all classes
in $T\sub 1$ except $J$. All the classes of $T\sub 2$ will be next.
The class $J$ and its superclasses will appear last.

\endsubSection%{Topological Sorting}

\beginsubSection{Examples}

This example determines a class precedence list for the
class {\tt pie}.  The following classes are defined:

\screen!

(defclass pie (apple cinnamon) ())

(defclass apple (fruit) ())

(defclass cinnamon (spice) ())

(defclass fruit (food) ())

(defclass spice (food) ())

(defclass food () ())
\endscreen!

The set $S$~$=$ $\{${\tt pie, apple, cinnamon, fruit, spice, food,
standard-object, t}$\}$. The set $R$~$=$ $\{${\tt (pie, apple),
(apple, cinnamon), (apple, fruit), (cinnamon, spice), (fruit, food),
\hfil\break (spice, food), (food, standard-object), (standard-object,
t)}$\}$.

The class {\tt pie} is not preceded by anything, so it comes first;
the result so far is {\tt (pie)}.  Remove {\tt pie} from $S$ and pairs
mentioning {\tt pie} from $R$ to get $S$~$=$ $\{${\tt apple, cinnamon,
fruit, spice, food, standard-object, t}$\}$ and $R$~$=$~$\{${\tt
(apple, cinnamon), (apple, fruit), (cinnamon, spice), (fruit,
food),\hfil\break (spice, food), (food, standard-object),
(standard-object, t)}$\}$.

The class {\tt apple} is not preceded by anything, so it is next; the
result is {\tt (pie apple)}. Removing {\tt apple} and the relevant
pairs results in $S$~$=$ $\{${\tt cinnamon, fruit, spice, food,
standard-object, t}$\}$ and $R$~$=$ $\{${\tt (cinnamon, spice),
(fruit, food), (spice, food), (food, standard-object),\hfil\break
(standard-object, t)}$\}$.

The classes {\tt cinnamon} and {\tt fruit} are not preceded by
anything, so the one with a direct subclass rightmost in the class
precedence list computed so far goes next.  The class {\tt apple} is a
direct subclass of {\tt fruit}, and the class {\tt pie} is a direct
subclass of {\tt cinnamon}.  Because {\tt apple} appears to the right
of {\tt pie} in the precedence list, {\tt fruit} goes next, and the
result so far is {\tt (pie apple fruit)}.  $S$~$=$ $\{${\tt cinnamon,
spice, food, standard-object, t}$\}$; $R$~$=$ $\{${\tt (cinnamon,
spice), (spice, food),\hfil\break (food, standard-object),
(standard-object, t)}$\}$.

The class {\tt cinnamon} is next, giving the result so far as {\tt
(pie apple fruit cinnamon)}.  At this point $S$~$=$ $\{${\tt spice,
food, standard-object, t}$\}$; $R$~$=$ $\{${\tt (spice, food), (food,
standard-object), (standard-object, t)}$\}$.

The classes {\tt spice}, {\tt food}, {\tt standard-object}, and {\tt
t} are added in that order, and the class precedence list is {\tt (pie
apple fruit cinnamon spice food standard-object t)}.

It is possible to write a set of class definitions that cannot be 
ordered.   For example: 

\screen!

(defclass new-class (fruit apple) ())

(defclass apple (fruit) ())
\endscreen!

The class {\tt fruit} must precede {\tt apple} because the local
ordering of superclasses must be preserved.  The class {\tt apple} must
precede {\tt fruit} because a class always precedes its own
superclasses.  When this situation occurs, an error is signaled when
the system tries to compute the class precedence list.

%End Part 2 of 6 concep.tex